package cn.zifangsky.linkedlist;

import java.util.Collection;
import java.util.function.Consumer;

/**
 * 使用双向链表实现的list
 *
 * @author zifangsky
 * @date 2019/9/4
 * @since 1.0.0
 */
public class LinkedList<E>{
    /**
     * 节点信息
     */
    private static class Node<E> {
        E item;
        Node<E> next;
        Node<E> prev;

        Node(Node<E> prev, E element, Node<E> next) {
            this.item = element;
            this.next = next;
            this.prev = prev;
        }
    }

    /* ---------------- Fields -------------- */
    /**
     * list的大小
     */
    private int size = 0;

    /**
     * 头结点
     */
    private Node<E> first;

    /**
     * 尾节点
     */
    private Node<E> last;

    public LinkedList() {
    }

    public LinkedList(Collection<? extends E> c) {
        this.addAll(c);
    }

    /**
     * 将新节点关联到链表首部
     */
    private void linkToFirst(E e){
        Node<E> f = this.first;
        //1. 创建新节点
        Node<E> newNode = new Node<>(null, e, f);

        //2. 跟以前的首节点关联
        this.first = newNode;

        if(f == null){
            this.last = newNode;
        }else{
            f.prev = newNode;
        }

        //3. list的大小+1
        this.size++;
    }

    /**
     * 将新节点关联到链表尾部
     */
    private void linkToLast(E e){
        Node<E> l = this.last;
        //1. 创建新节点
        Node<E> newNode = new Node<>(l, e, null);

        //2. 跟以前的尾节点关联
        this.last = newNode;

        if(l == null){
            this.first = newNode;
        }else{
            l.next = newNode;
        }

        //3. list的大小+1
        this.size++;
    }

    /**
     * 将新节点关联到指定节点的前面
     */
    private void linkToLeft(E e, Node<E> current){
        if(current == null){
            return;
        }

        Node<E> prev = current.prev;
        //1. 创建新节点
        Node<E> newNode = new Node<>(prev, e, current);

        //2. 将新节点关联到链表
        if(prev == null){
            this.first = newNode;
        }else{
            prev.next = newNode;
        }

        //3. list的大小+1
        this.size++;
    }

    /**
     * 删除头结点
     */
    private E removeFirst(Node<E> f){
        if(f == null || (f != this.first)){
            throw new RuntimeException("Node f isn't the first node");
        }

        E element = f.item;
        Node<E> next = f.next;

        f.next = null;
        f.item = null;
        this.first = next;

        if(next == null){
            this.last = null;
        }else{
            next.prev = null;
        }

        this.size--;
        return element;
    }

    /**
     * 删除尾结点
     */
    private E removeLast(Node<E> l){
        if(l == null || (l != this.last)){
            throw new RuntimeException("Node l isn't the last node");
        }

        E element = l.item;
        Node<E> prev = l.prev;

        l.next = null;
        l.item = null;
        this.last = prev;

        if(prev == null){
            this.first = null;
        }else{
            prev.next = null;
        }

        this.size--;
        return element;
    }

    /**
     * 删除指定非空结点
     */
    private E remove(Node<E> node){
        if(node == null){
            throw new RuntimeException("Node cannot be empty!");
        }

        E element = node.item;
        Node<E> prev = node.prev;
        Node<E> next = node.next;

        node.item = null;

        if(prev == null){
            this.first = null;
        }else{
            prev.next = next;
            node.prev = null;
        }

        if(next == null){
            this.last = null;
        }else{
            next.prev = prev;
            node.next = null;
        }

        this.size--;
        return element;
    }

    /**
     * 查找指定数据的节点
     */
    private Node<E> find(Object o){
        if (o == null) {
            for (Node<E> node = this.first; node != null; node = node.next) {
                if (node.item == null) {
                    return node;
                }
            }
        } else {
            for (Node<E> node = this.first; node != null; node = node.next) {
                if (o.equals(node.item)) {
                    return node;
                }
            }
        }

        return null;
    }

    /**
     * 查找指定位置的节点
     */
    private Node<E> find(int index){
        this.checkElementIndex(index);

        if(index < (this.size >> 1)){
            Node<E> node = this.first;
            for(int i = 0; i < index; i++){
                node = node.next;
            }
            return node;
        }else{
            Node<E> node = last;
            for(int i = (this.size - 1); i > index; i--){
                node = node.prev;
            }
            return node;
        }
    }

    /**
     * 判断index是否合理
     */
    private boolean isElementIndex(int index) {
        return index >= 0 && index < this.size;
    }

    /**
     * 判断index是否合理
     */
    private boolean isPositionIndex(int index) {
        return index >= 0 && index <= size;
    }

    private void checkElementIndex(int index) {
        if (!isElementIndex(index)) {
            throw new IndexOutOfBoundsException("Index: " + index + ", Size: " + this.size);
        }
    }

    private void checkPositionIndex(int index) {
        if (!isPositionIndex(index)) {
            throw new IndexOutOfBoundsException("Index: " + index + ", Size: " + this.size);
        }
    }

    public void forEach(Consumer<E> action){
        if(!this.isEmpty()){
            for (Node<E> node = this.first; node != null; node = node.next) {
                action.accept(node.item);
            }
        }
    }

    public int size() {
        return this.size;
    }

    public boolean isEmpty() {
        return this.size() == 0;
    }

    public boolean contains(Object o) {
        return this.indexOf(o) != -1;
    }

    public Object[] toArray() {
        Object[] result = new Object[size];
        int i = 0;
        for (Node<E> node = this.first; node != null; node = node.next) {
            result[i++] = node.item;
        }
        return result;
    }

    public <T> T[] toArray(T[] a) {
        int i = 0;
        Object[] result = a;
        for (Node<E> node = this.first; node != null; node = node.next) {
            result[i++] = node.item;
        }

        if (a.length > size) {
            a[size] = null;
        }

        return a;
    }

    public boolean add(E e) {
        this.linkToLast(e);
        return true;
    }

    public void add(int index, E element) {
        this.checkPositionIndex(index);

        if(index == this.size){
            this.linkToLast(element);
        }else{
            this.linkToLeft(element, this.find(index));
        }
    }

    public boolean addAll(Collection<? extends E> c) {
        if(c != null && !c.isEmpty()){
            for (E e : c) {
                this.add(e);
            }
        }

        return true;
    }

    public boolean addAll(int index, Collection<? extends E> c) {
        Object[] a = c.toArray();
        int numNew = a.length;
        if (numNew == 0) {
            return false;
        }

        Node<E> prev, current;
        if (index == size) {
            current = null;
            prev = last;
        } else {
            current = this.find(index);
            prev = current.prev;
        }

        for (Object o : a) {
            @SuppressWarnings("unchecked")
            E e = (E) o;
            Node<E> newNode = new Node<>(prev, e, null);
            if (prev == null) {
                first = newNode;
            } else {
                prev.next = newNode;
            }
            prev = newNode;
        }

        if (current == null) {
            last = prev;
        } else {
            prev.next = current;
            current.prev = prev;
        }

        size += numNew;
        return true;
    }

    public boolean remove(Object o) {
        Node<E> node = this.find(o);

        if(node != null){
            this.remove(node);
            return true;
        }

        return false;
    }

    public E remove(int index) {
        this.checkElementIndex(index);

        return this.remove(this.find(index));
    }

    public boolean containsAll(Collection<?> c) {
        if(c != null && !c.isEmpty()){
            for (Object e : c) {
                if (!this.contains(e)) {
                    return false;
                }
            }
        }

        return true;
    }

    public void clear() {
        for (Node<E> node = this.first; node != null; ) {
            Node<E> next = node.next;
            node.item = null;
            node.next = null;
            node.prev = null;
            node = next;
        }

        this.size = 0;
        this.first = null;
        this.last = null;
    }

    public E get(int index) {
        return this.find(index).item;
    }

    public E set(int index, E element) {
        this.checkElementIndex(index);

        Node<E> node = this.find(index);

        E oldVal = node.item;
        node.item = element;
        return oldVal;
    }

    public int indexOf(Object o) {
        int index = 0;
        if (o == null) {
            for (Node<E> node = this.first; node != null; node = node.next) {
                if (node.item == null) {
                    return index;
                }
                index++;
            }
        } else {
            for (Node<E> node = this.first; node != null; node = node.next) {
                if (o.equals(node.item)) {
                    return index;
                }
                index++;
            }
        }

        return -1;
    }

    public int lastIndexOf(Object o) {
        int index = size;
        if (o == null) {
            for (Node<E> node = this.last; node != null; node = node.prev) {
                index--;
                if (node.item == null) {
                    return index;
                }
            }
        } else {
            for (Node<E> node = this.last; node != null; node = node.prev) {
                index--;
                if (o.equals(node.item)) {
                    return index;
                }
            }
        }

        return -1;
    }

    /**
     * 获取头结点（但是不删除）
     */
    public E top() {
        return this.peek();
    }

    /**
     * 获取头结点（但是不删除）
     */
    public E peek() {
        return this.peekFirst();
    }

    /**
     * 获取头结点（但是不删除）
     */
    public E peekFirst() {
        final Node<E> f = this.first;
        return (f == null) ? null : f.item;
    }

    /**
     * 获取尾结点（但是不删除）
     */
    public E peekLast() {
        final Node<E> l = this.last;
        return (l == null) ? null : l.item;
    }

    /**
     * 获取头结点（并删除）
     */
    public E poll() {
        return this.pollFirst();
    }

    /**
     * 获取头结点（并删除）
     */
    public E pollFirst() {
        final Node<E> f = this.first;
        return (f == null) ? null : this.removeFirst(f);
    }

    /**
     * 获取尾结点（并删除）
     */
    public E pollLast() {
        final Node<E> l = this.last;
        return (l == null) ? null : this.removeLast(l);
    }

    /**
     * 入栈
     */
    public void push(E e) {
        this.linkToFirst(e);
    }

    /**
     * 出栈
     */
    public E pop() {
        return this.pollFirst();
    }

    /**
     * 添加到末尾
     */
    public boolean offer(E e) {
        return this.offerLast(e);
    }

    /**
     * 添加到头部
     */
    public boolean offerFirst(E e) {
        this.linkToFirst(e);
        return true;
    }

    /**
     * 添加到末尾
     */
    public boolean offerLast(E e) {
        this.linkToLast(e);
        return true;
    }
}
